package com.julius.design.suanfa.sort;

import java.util.Arrays;

/**
 * @author julius
 * @date 2021-11-10 上午 10:13
 * <p>
 *      把数组排成最小的数
 *      输入一个非负整数数组，把数组里所有数字拼接起来排成一个数，打印能拼接出的所有数字中最小的一个
 *
 *      https://leetcode-cn.com/problems/ba-shu-zu-pai-cheng-zui-xiao-de-shu-lcof/
 * </p>
 */
public class MinNumber {


    /**
     * 将一个数组拼接为最小的数
     * [10,2] 102
     * [3,300012,300124,32,33,5,9,1000,110,102] 30 31 32 33 3 5 9   30313233359
     *
     *
     *
     * 将数组排序（升序）：
     *      这里的排序规则需要发生变化,
     *      数字按照指定规则排序
     *          1. 转为字符串
     *          2. x + y > y+x  x排在y的后面  否则x排在y的前面
     *          3. 拼接字符串数组
     *
     * @param nums
     * @return
     */
    public String minNumber(int[] nums){

        if(nums.length == 1){
            return String.valueOf(nums[0]);
        }
        String[] strs = new String[nums.length];
        //转换
        for (int i = 0; i < nums.length ; i++) {
            strs[i] = String.valueOf(nums[i]);
        }

        //自定义排序（快速排序或者内置函数）
        Arrays.sort(strs,(x,y)->(x+y).compareTo(y+x));
        StringBuilder ans = new StringBuilder();
        for (int i = 0; i < strs.length; i++) {
            ans.append(strs[i]);
        }
        return ans.toString();



    }

    public static void sort(int[] nums){
        //双指针冒泡排序
        int right = nums.length - 1;
        while(right != 0){
            int left = 0;
            while(left < right){
                if(nums[left] >= nums[right]){
                    int temp = nums[left];
                    nums[left] = nums[right];
                    nums[right] = temp;
                }
                left++;
            }
            right--;
        }
    }

    public static boolean isStraight(int[] nums) {
        // 1 2-10 11 12 13 1  0 0 看相差是不是为1 ，否则相差多少就要使用k-1个0 代替

        //首先给数组排序
        sort(nums);

        //判断是否连续
        int zeroNum = 0;
        for(int i = 0;i< nums.length-1;i++){
            if(nums[i] == 0){
                //万能牌个数
                zeroNum++;
                continue;
            }else{
                if(nums[i+1] - nums[i] == 0){
                    return false;
                }else if(nums[i+1]-nums[i] == 1){
                    continue;
                }else{
                    int temp = nums[i+1]-nums[i]-1;
                    if(temp > zeroNum){
                        return false;
                    }else{
                        zeroNum-=temp;
                    }
                }
            }
        }
        return true;
    }


    public static void main(String[] args) {
        int[] nums = new int[]{0,1,12,11,10};
//        sort(nums);
        for (int i = 0; i < nums.length; i++) {
            System.out.print(nums[i]+" ");
        }
        System.out.println(isStraight(nums));
    }

}
